/*
 * source:		自定义题目，退化后的FireNet问题，同时可以引导解决8皇后问题
 *  NSquare Problem
 *  输出N＊N方格中放置棋子的具体方式，要求棋子之间相互不同行、同列
 *	Author: Dspark
 *	Date:	11.1,		2011
 */

#include<stdio.h>
#include<stdlib.h>

#define N 5

typedef struct SPosition
{
	int x,y;
}position;

typedef struct SStack
{
	int index;
	position stack[N];
}stack;

stack s = {-1};
int result=0;

int util_stack_push(int x,int y)
{
	s.index++;
	s.stack[s.index].x = x;
	s.stack[s.index].y = y;
	return s.index;
}

position* util_stakc_pop()
{
	int j = s.index;
	s.index--;
	return &(s.stack[j]);
}

void util_stack_output()
{
	int i;
	for(i=0;i<=s.index;i++)
	{
		printf("第%d个 放置在(%d,%d)\t",		i,	s.stack[i].x,	s.stack[i].y);
	}
	printf("放置结束\n");
}

int check(int x, int y)
{
	int i;
	for(i=0;	i<=s.index;	i++)
	{
		if(x==s.stack[i].x  ||	y==s.stack[i].y)
			return 0;
	}
	return 1;
}

void Nsquare(int x,int y)
{
	if(y == 0 && x==N)
			return;
	if(s.index<=-1)
	{
			util_stack_push(x,	y);
			Nsquare(0,y+1);
			return;
	}

	if(x==N)
	{
			position* temp = util_stakc_pop();
//			printf("第%d行检测完毕，退回到上一层从%d处开始检测\n",	temp->x+1,	temp->y);
			Nsquare(temp->x+1 ,	temp->y);
			return;
	}
	if(check(x,y)==1)
	{
//		printf("位置不冲突，可以进栈\n");
		util_stack_push(x,y);
		if(s.index<N-1)
		{
//			printf("尚未排满，继续进栈!\n");
			Nsquare(0, y+1);
			return;
		}
		else if(s.index==N-1)
		{

			result++;
			printf("找到了第%d种方法，实现方式如下:\n",result);
			util_stack_output();
			util_stakc_pop();
			position* temp = util_stakc_pop();
			Nsquare(temp->x+1 ,temp->y);
			return;
		}
	}
	else
	{
//		printf("该位置不可用，检测下一位 \n");
		Nsquare(x+1,	y);
		return;
	}
}

int main(int argc, char **argv) {
//	printf("开始分配内存.\n");
	Nsquare(0,0);
	printf("总共有%d种方法\n",result);
	return 0;
}


